本节我们学习两种关键的基本算法思想：DFS（深度优先搜索）和BFS（广度优先搜索）。这两种算法和栈、队列有着千丝万缕的关系，如果前两节你认真学习掌握了，那么这一节对你来说相信不是问题。

深度优先搜索思想：不撞南墙不回头的“迷宫游戏”

⚡ 30 秒速记

• DFS（深度优先）= 走迷宫一条路走到底，撞墙了退回最近的岔路口换一条
• 实现：递归（借函数调用栈）或手写栈，本质都是后进先出
• 图里有环，必须在入栈时标记 visited，否则会重复访问甚至死循环
• 复杂度 O(V + E)；递归深度由树高或最长路径决定
• 适合枚举路径、连通性、回溯；不保证无权图最短路，最短路找 BFS

DFS 就是走迷宫的笨办法：认准一条路往里走，走不通就退回上一个岔路口换条路。 实现上有两种写法，一种是递归，函数调用栈帮你记住回退点；一种是自己维护一个数组当栈，pop 一个处理一个，把邻居 push 进去。两种本质一样，都是后进先出。遍历图的时候我会在节点第一次入栈时就加进 visited，不然有环的图会转圈。它能找到「一条」出路，但不保证是最短的，要最少步数得换 BFS。

回答参考：“DFS 的核心不是递归语法，而是后进先出的待办集合。我会先定义访问标记时机，再说明当前路径与已完成节点各代表什么。”

function dfs(graph, start) {
  if (start == null) return []
  const stack = [start]
  const visited = new Set([start])
  const order = []

  while (stack.length) {
    const node = stack.pop()
    order.push(node)
    const neighbors = graph.get(node) ?? []
    for (let i = neighbors.length - 1; i >= 0; i -= 1) {
      const next = neighbors[i]
      if (!visited.has(next)) {
        visited.add(next)
        stack.push(next)
      }
    }
  }
  return order
}

💬 面试官追问

• 把递归改成手写 stack 之后，还算 DFS 吗？

  算。DFS 看的是处理顺序是不是后进先出，不看你有没有写递归。递归只是借用了 JS 引擎的调用栈，手写栈还能躲开 Maximum call stack size exceeded。

• 同一张图，递归版顺序是 A B C，改成栈版变成了 A C B，怎么回事？

  栈后进先出，邻居按 B、C 正序压进去，C 就先弹出来。想和递归顺序一致，就从邻接表末尾往前压：for (let i = nbrs.length - 1; i >= 0; i--)。

• visited 放在 pop() 之后再标记，有什么问题？

  结果大概率还是对的，但同一个节点会被多个邻居反复压栈，栈的峰值能涨到边数级别。一般在 push 的时候就标记，从源头挡掉重复。

• 找到出口后还要把路线画出来，怎么记路径？

  发现新节点时记一笔 parent.set(next, node)，到出口后顺着 parent 倒推回起点再 reverse()。别直接拿栈当路径，普通遍历栈里混着别的分支的待办节点，连不成一条线。